package com.tim.test.leetcode.exam;


public class HuaWei20240201 {

    /**
     输入一个链表，输出该链表中倒数第k个节点。从1开始计数，即链表的尾节点是倒数第1个节点。
     例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
     示例：
     给定一个单向链表: 1->2->3->4->5, 和 k = 2.
     返回链表 4->5.

     自定义node、queue
     */
    public static void main(String[] args) {
        HuaWei20240201 m = new HuaWei20240201();
        NodeQueue nodeQueue = new NodeQueue();
        for(int i=1; i<6; i++){
            Node node = new Node();
            node.setVal(i+"");
            nodeQueue.addNode(node);
        }
        NodeQueue result = m.getSubQueue(nodeQueue, 1);
        System.out.println(result);
    }

    public NodeQueue getSubQueue(NodeQueue nodeQueue, int k){
        if(nodeQueue==null||nodeQueue.tail==null){
            return null;
        }
        if(k<1){
            return null;
        }
        // 尾结点向前遍历；找到倒数第k个节点。result.head=kNode
        NodeQueue result = new NodeQueue();
        Node first = null;
        Node second = null;
        for (int i = 0; i < k; i++) {
            // 快k步
            first = first==null ? nodeQueue.head : first.getAfter();
        }
        while(first.after!=null){
            first = first.getAfter();
            second = second==null ? nodeQueue.head : second.getAfter();
        }
        result.setHead(second.after);
        return result;
    }

    static class Node {

        private Node after;

        private String val;

        public Node getAfter() {
            return after;
        }

        public void setAfter(Node after) {
            this.after = after;
        }

        public String getVal() {
            return val;
        }

        public void setVal(String val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val+(after==null ? "" : "->"+after);
        }
    }

    static class NodeQueue {
        private Node head;
        private Node tail;

        public void addNode(Node node){
            if(head==null){
                // 空链表
                head = node;
            }else if(head!=null){
                if(head.getAfter()==null){
                    head.setAfter(node);
                }else{
                    tail.setAfter(node);
                }
                tail = node;
            }
        }

        public Node getHead() {
            return head;
        }

        public void setHead(Node head) {
            this.head = head;
        }

        @Override
        public String toString() {
            return head.toString();
        }
    }
}